package BackTrack;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * 表面看起来是 超一轮 收集 res
 *
 * -> 其实是 下一轮if卡住了 没走for（其实没超）
 */
public class 组合77 {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> tmp = new ArrayList<>();
    int n,k;
    int[] nums;
    public List<List<Integer>> combine(int n, int k) {
        this.n = n;
        this.k = k;
        nums = new int[n]; //内部new，要不爱少this
        for (int i = 0; i < n; i++) {
            nums[i]= i+1;
        }
        // 不用多起点
        // for (int i = 0; i < n; i++) {
        backTrack(0);
        // }
        return res;
    }
    void backTrack(int startIndex) {
        if(tmp.size() == k){
            res.add(new ArrayList<>(tmp));
            return;
        }
        for (int i = startIndex; i < n
                && tmp.size()+n+1-i >= k
                ; i++) {
            tmp.add(nums[i]);
            backTrack(i+1);
            tmp.remove(tmp.size()-1);
        }
    }

     @Test
     public void test(){
         System.out.println(combine(4, 2));
     }
}
